
def LCSubstr_len(S, T):
     m = len(S); n = len(T)
     L = [[0] * (n+1) for i in xrange(m+1)]
     lcs = 0
     for i in xrange(m):
         for j in xrange(n):
             if S[i] == T[j]:
                 L[i+1][j+1] = L[i][j] + 1
                 lcs = max(lcs, L[i+1][j+1])
     return lcs
 
def LCSubstr_set(S, T):
     m = len(S); n = len(T)
     L = [[0] * (n+1) for i in xrange(m+1)]
     lcs = 0
     LCS = set()
     longest = 0
     for i in xrange(m):
         for j in xrange(n):
             if S[i] == T[j]:
                 v = L[i][j] + 1
                 L[i+1][j+1] = v
                 if v > longest:
                     longest = v
                     LCS = set()
                 if v == longest:
                     LCS.add(S[i-v+1:i+1])
     return LCS

def levenshtein(a, b):
     if not a:
         return len(b)
     if not b:
         return len(a)
     return min(int(a[0] != b[0]) + levenshtein(a[1:], b[1:]),
         1 + levenshtein(a[1:], b),
         1 + levenshtein(a, b[1:]))

def cmp(a, b):
    d = 0
    if (len(a)>len(b)):
        d = len(a)-len(b)
        for i in range(len(b)):
            if (a[i] != b[i]):
                d = d+1
    else:
        d = len(b)-len(a)
        for i in range(len(a)):
            if (a[i] != b[i]):
                d = d+1
    return d
def distance(a, b):
     sub = LCSubstr_len(a,b)
     print sub
     if (len(a)>len(b)):
             longest = len(a)
     else:
             longest=len(b)
     return 1-(float(sub)/longest)
 


